home *** CD-ROM | disk | FTP | other *** search
/ Internet Publisher's Toolbox 2.0 / Internet Publisher's Toolbox.iso / internet / ntserver / wtsource / trie.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-03-10  |  6.4 KB  |  329 lines
  1. /* WIDE AREA INFORMATION SERVER SOFTWARE:
  2.    No guarantees or restrictions.  See the readme file for the full standard
  3.    disclaimer.
  4. */
  5.  
  6. /* Copyright (c) CNIDR (see ../COPYRIGHT) */
  7.  
  8.  
  9. #ifndef lint
  10. static char *RCSid = "$Header: /usr/users/freewais/FreeWAIS-0.1/ir/trie.c,v 1.1 1993/02/16 15:05:35 freewais Exp $";
  11. #endif
  12.  
  13. /* Change log:
  14.  * $Log: trie.c,v $
  15.  * Revision 1.1  1993/02/16  15:05:35  freewais
  16.  * Initial revision
  17.  *
  18.  * Revision 1.2  92/02/12  13:52:49  jonathan
  19.  * Added "$Log" so RCS will put the log message in the header
  20.  * 
  21.  * 
  22. */
  23.  
  24. /*
  25.   trie.c: This module provides an associative lookup table, based on
  26.   tries [see Knuth,D. Art of Computer Programming, Vol 3]
  27.  
  28.   Author: Simon E Spero (ses@ccgr.technion.ac.il)
  29.   This file is in the public domain.
  30.  
  31.   public functions:
  32.   
  33.   encode: encodes a string for searching
  34.  
  35.   make_trie_allocator: contructs a trie allocator
  36.   dispose_trie_allocator: dispose of a trie
  37.  
  38.   new_trie(string): 
  39.     creates a new trie containing only the entry `string'
  40.     
  41.   trie_lookup(word,dictionary,allocator).
  42.    This function looks up word in the dictionary, and, if found,
  43.    returns a pointer to it's datum. If the word is not found,
  44.    and allocator != NULL, the word will be added to the dictionary.
  45.    If an error occurs, the function returns NULL
  46. */
  47.   
  48.  
  49. #include <ctype.h>
  50. #include <stdio.h>
  51. #include "cutil.h"
  52. #include "trie.h"
  53.  
  54. /*
  55.  * Special purpose allocators for resources that are freed only in bulk
  56.  */
  57.  
  58. /*
  59.  * make a new allocator 
  60.  */
  61. #ifdef WIN32
  62. allocator* make_allocator(int item_size, void (*free_func)(char*))
  63. #else
  64. allocator* make_allocator(item_size,free_func) 
  65. int item_size;
  66. void (*free_func)();
  67. #endif
  68. {
  69.   allocator* tmp;
  70.   if (!(tmp = (allocator *)s_malloc(sizeof(allocator)))) {
  71.     return 0L;
  72.   }
  73.  
  74.   tmp->size=item_size;
  75.   tmp->dispose = free_func;
  76.   return tmp;
  77. }
  78.  
  79. /*
  80.  * dispose of an allocator
  81.  */
  82. void fast_free(alloc)
  83. allocator* alloc;
  84. {
  85.   
  86.   char *block;
  87.   int i,j;
  88.   int limit;
  89.   for(i=0;i<alloc->blocks_allocated;i++) {
  90.     if(alloc->dispose) {
  91.       block=alloc->tofree[i];
  92.       limit = (i+1 == alloc->blocks_allocated ? CHUNK_SIZE - alloc->items_left : CHUNK_SIZE);
  93.       for(j=0;j<limit;j++) {
  94.         alloc->dispose(block);
  95.         block += alloc->size;
  96.       }
  97.     }
  98.     free(alloc->tofree[i]);
  99.   }
  100. }
  101.  
  102. /*
  103.  * allocate an item
  104.  */
  105.  
  106. char* fast_alloc(alloc)
  107. allocator* alloc;
  108. {
  109.   
  110.   char* tmp;
  111.  
  112.   if (!alloc->items_left) {
  113.     if (alloc->blocks_allocated <MAX_BLOCKS &&
  114.         (tmp = (char *)s_malloc(alloc->size*CHUNK_SIZE))) {
  115.       alloc->tofree[alloc->blocks_allocated++] = tmp;
  116.       alloc->next_location = tmp +alloc->size;
  117.       alloc->items_left = CHUNK_SIZE-1;
  118.       return tmp;
  119.     } else {
  120.       return 0L;
  121.     }
  122.   } else {
  123.     tmp = alloc->next_location;
  124.     alloc->next_location += alloc->size;
  125.     alloc->items_left--;
  126.     return tmp;
  127.   }
  128. }
  129.  
  130. /*
  131.  * function to free non fast_alloced stuff from a trie.
  132.  *   should really be a lambda expression, but....
  133.  */
  134.  
  135. void  free_trie(dict)
  136. trie* dict;
  137. {
  138.   free(dict->string);
  139. }
  140.  
  141. /*
  142.  * make an allocator for tries
  143.  */
  144.  
  145. trie_allocator* make_trie_allocator()
  146. {
  147.   trie_allocator* tmp;
  148.   if(!(tmp = (trie_allocator*)s_malloc(sizeof(trie_allocator)))) {
  149.     return 0L;
  150.   }
  151. #ifdef WIN32
  152.   if (!(tmp->tries = make_allocator(sizeof(trie),(void *)free_trie))) {
  153. #else
  154.   if (!(tmp->tries = make_allocator(sizeof(trie),free_trie))) {
  155. #endif
  156.     free(tmp);
  157.     return 0L;
  158.   }
  159. #ifdef WIN32
  160.   if (!(tmp->trie_tables = make_allocator(sizeof(trie_table),(void *)0L))) {
  161. #else
  162.   if (!(tmp->trie_tables = make_allocator(sizeof(trie_table),0L))) {
  163. #endif
  164.     free(tmp->tries);
  165.     free(tmp);
  166.     return 0L;
  167.   }
  168.   return tmp;
  169. }
  170.  
  171. /*
  172.  * dispose of a trie
  173.  */
  174.  
  175. void dispose_trie_allocator(alloc)
  176. trie_allocator* alloc;
  177. {
  178.   fast_free(alloc->tries);
  179.   fast_free(alloc->trie_tables);
  180.   free(alloc);
  181. }
  182.  
  183. /*
  184.  * make a trie with str as it's only entry
  185.  */
  186.  
  187. trie* new_trie(str,alloc)
  188. char* str;
  189. trie_allocator* alloc;
  190. {
  191.   trie* tmp;
  192.  
  193.   tmp=(trie*)fast_alloc(alloc->tries);
  194.   tmp->string=s_strdup(str);
  195.   tmp->table=0L;
  196.   tmp->datum=0L;
  197.   return tmp;
  198. }
  199.  
  200. trie ** new_trie_table(alloc)
  201. allocator* alloc; {
  202.  
  203.   trie** tmp;
  204.  
  205.   tmp=(trie **)fast_alloc(alloc);
  206.   if(!tmp) {
  207.     return 0L;
  208.   }
  209.   return tmp;
  210. }
  211.  
  212. /*
  213.   After all those allocators, finally a useful function! 
  214.   */
  215.  
  216. void **trie_lookup(key,dict,alloc)
  217.      char* key;
  218.      trie* dict;
  219.      trie_allocator* alloc;
  220. {
  221.  
  222.   char *c,*d;
  223.   trie *t,*t2;
  224.  
  225.   c = key;
  226.   d = dict->string;
  227.  
  228.   while(*c && *d && *c == *d) {
  229.     c++; d++;
  230.   }
  231.  
  232.   if (!*c ) { 
  233.     if(!*d) {
  234.       /* we found the answer*/
  235.       return &(dict->datum);
  236.     }
  237.     /* key was a prefix*/
  238.     if (!alloc) {
  239.       return 0L;
  240.     }
  241.     /* split this node */
  242.     t = new_trie(d+1,alloc);
  243.     t->table = dict->table;
  244.     t->datum = dict->datum;
  245.     dict->table= (trie **)new_trie_table(alloc->trie_tables);
  246.     dict->table[*d]=t;
  247.     dict->datum=0L;
  248.     dict->string=s_strdup(key);
  249.     return &(dict->datum);
  250.   }
  251.  
  252.   if(*d && *c != *d) { /* mismatch */
  253.     if (!alloc) {
  254.       return 0L;
  255.     }
  256.     t  = new_trie(d+1,alloc);
  257.     t2 = new_trie(c+1,alloc);
  258.     t->datum=dict->datum;
  259.     t->table=dict->table;
  260.     dict->table= (trie **)new_trie_table(alloc->trie_tables);
  261.     dict->table[*c] = t2;
  262.     dict->table[*d] = t;
  263.     dict->datum =0L;
  264.     *d='\0';
  265.     return &(t2->datum);
  266.   }
  267.   
  268.   /*
  269.     Follow the pointers in table, if there are any
  270.     */
  271.   if (!dict->table) {
  272.     if (!alloc) {
  273.       return 0L;
  274.     }
  275.     dict->table=(trie **)new_trie_table(alloc->trie_tables);
  276.   }
  277.   
  278.   if(dict->table[*c]) {
  279.     return trie_lookup(c+1,dict->table[*c],alloc);
  280.   } else {
  281.     if (!alloc) {
  282.       return 0L;
  283.     }
  284.     dict->table[*c] = new_trie(c+1,alloc);
  285.     return &(dict->table[*c]->datum);
  286.   }
  287.  
  288. }
  289.  
  290. /*
  291.   WARNING: IF CHECK_ALNUM IS UNDEFINED, MAKE SURE YOU PASS IN AN ALNUM,
  292.   OR ELSE
  293. */
  294.  
  295. int encode( s)
  296. unsigned char* s; {
  297.   register unsigned char * e;
  298. #ifndef WIN32
  299.   unsigned char t;
  300. #endif
  301.   for(e=s;*e;e++) {
  302. #ifdef CHECK_ALNUM
  303.     if (!isalnum(*e)) {
  304.       return 0;
  305.     }
  306. #endif
  307.     if (isdigit(*e)) {
  308.       *e = *e -'0' + 27;
  309.     } else {
  310.       *e = (*e & 31);
  311.     }
  312.   }
  313.   return 1;
  314. }
  315.  
  316.  
  317. void decode(s) 
  318. unsigned char* s;
  319. {
  320.   while(*s) {
  321.     if (*s < 27) {
  322.       *s += ('a'-1);
  323.     } else {
  324.       *s += ('0'-27);
  325.     }
  326.     *s++;
  327.   }
  328. }
  329.